#include <stdio.h>
#include <assert.h>
#include<unistd.h>
#include "rb_tree.h"

inline rb_node_t *rb_parent(rb_node_t *node)
{
	return node->parent;
}       

inline int rb_color(rb_node_t *node)
{       
	return node->color;
}       

inline int rb_is_red(rb_node_t *node)
{       
	return node->color == RB_RED;
}               

inline int rb_is_black(rb_node_t *node)
{                       
	return node->color == RB_BLACK;
}

inline void rb_set_red(rb_node_t *node)
{       
	node->color = RB_RED;
}       

inline void rb_set_black(rb_node_t *node)
{
	node->color = RB_BLACK;
}

inline void rb_set_parent(rb_node_t *node, rb_node_t *p)
{
	node->parent = p;
}

inline void rb_set_color(rb_node_t *node, int color)
{
	node->color = color;
}

inline void rb_link_node(rb_node_t * node, rb_node_t * parent,
		rb_node_t ** rb_link)
{
	node->parent = parent;
	node->rb_left = node->rb_right = NULL;
	*rb_link = node;
}

rb_node_t *rb_first(rb_root_t *root)
{
	rb_node_t *n;

	n = root->node;
	if (!n)
		return NULL;
	while (n->rb_left)
		n = n->rb_left;
	return n;
}

rb_node_t *rb_last(rb_root_t *root)
{
	rb_node_t *n;

	n = root->node;
	if (!n)
		return NULL;
	while (n->rb_right)
		n = n->rb_right;
	return n;
}

rb_node_t *rb_next(rb_node_t *node)
{
	rb_node_t *p;

	if (node->rb_right) {
		node = node->rb_right;
		while(node->rb_left)
			node = node->rb_left;
		return node;
	}
	while((p = rb_parent(node)) && node == p->rb_right)
		node = p;
	return p;
}

rb_node_t *rb_prev(rb_node_t *node)
{
	rb_node_t *p;
	
	if (node->rb_left) {
		node = node->rb_left;
		while (node->rb_right) 
			node = node->rb_right;
		return node;
	}
	while ((p = rb_parent(node)) && node == p->rb_left)
		node = p;

	return p;
}

void __rb_rotate_left(rb_node_t *node, rb_root_t *root)
{
	rb_node_t *r = node->rb_right;
	rb_node_t *p = rb_parent(node);

	/* move right's left to node's right */
	if ((node->rb_right = r->rb_left))
		rb_set_parent(r->rb_left, node);
	
	/* move node to right's left */
	r->rb_left = node;
	rb_set_parent(node, r);
	
	/* move right to parent's sun */
	if (p) {
		if (node == p->rb_left)
			p->rb_left = r;
		else 
			p->rb_right = r;
	} else 
		root->node = r;
	rb_set_parent(r, p);
}

void __rb_rotate_right(rb_node_t *node, rb_root_t *root)
{
	rb_node_t *l = node->rb_left;
	rb_node_t *p = rb_parent(node);
	
	/* move left's right to node's left */
	if ((node->rb_left = l->rb_right))
		rb_set_parent(l->rb_right, node);

	/* move node to left's right */
	l->rb_right = node;
	rb_set_parent(node, l);

	/* move left to parent's sun */
	if (p) {
		if (node == p->rb_left)
			p->rb_left = l;
		else 
			p->rb_right = l;
	} else 
		root->node = l;
	rb_set_parent(l, p);
}

void rb_insert_color(rb_node_t *node, rb_root_t *root)
{
	rb_node_t *p, *gp, *uk;
	
	/* the node we insert is red
	 * if the parent is black, we stop fixup
	 */
	while ((p = rb_parent(node)) && rb_is_red(p)) {
		gp = rb_parent(p);
	
		/* parent is grandpa's left */
		//printf("p->data:%d:gp->data:%d\n", p->data, gp->data);
		fsync(1);
		if (p == gp->rb_left) {
			uk = gp->rb_right;
			/* uncle is red */
			if (uk && rb_is_red(uk)) {
				rb_set_black(p);
				rb_set_black(uk);
				rb_set_red(gp);
				node = gp;
				continue;
			} 
			/* node is parent's right */
			if (node == p->rb_right) {
				rb_node_t *tmp;
				__rb_rotate_left(p, root);
				tmp = node;
				node = p;
				p = tmp;
			}
			/* node is parent's left */
			rb_set_black(p);
			rb_set_red(gp);
			__rb_rotate_right(gp, root);
			//assert(rb_is_red(rb_parent(node)));
		} else {
			uk = gp->rb_right;
			if (uk && rb_is_red(uk)) {
				rb_set_black(p);
				rb_set_black(uk);
				rb_set_red(gp);
				node = gp;
				continue;
			} 

			if ((node = p->rb_left) != NULL) {
				rb_node_t *tmp;
				__rb_rotate_right(p, root);
				tmp = node;
				node = p;
				p = node;
			}
			rb_set_black(p);
			rb_set_red(gp);
			__rb_rotate_left(gp, root);
			//assert(rb_is_red(rb_parent(node)));
		}
	}
	rb_set_black(root->node);
}

static void __rb_erase_color(rb_node_t *node, 
		rb_node_t *parent, rb_root_t *root)
{
	rb_node_t *other = NULL;

	while ((!node || rb_is_black(node)) && node != root->node) {
		if (node == parent->rb_left) {
			other = parent->rb_right;

			//if (other && rb_is_red(other)) {
			if (other && rb_is_red(other)) {
				rb_set_red(parent);
				rb_set_black(other);
				__rb_rotate_left(parent, root);
				other = parent->rb_right;
			}
			//if (other && (other->rb_left && rb_is_black(other->rb_left))
			if ((!other->rb_left || rb_is_black(other->rb_left))
				&& (!other->rb_right || rb_is_black(other->rb_right))) {
				/* we don't need to judge if the parent is black */
				/*
				rb_set_red(other);
				if (rb_is_black(parent)) {
					node = parent;
					parent = rb_parent(parent);
					continue;
				}
				rb_set_black(parent);
				break;
				*/
				rb_set_red(other);
				node = parent;
				parent = rb_parent(parent);
			} else {
				//if (other && (other->rb_left && rb_is_red(other->rb_left))) {
				if (other->rb_left && rb_is_red(other->rb_left)) {
					rb_set_black(other->rb_left);
					rb_set_red(other);
					__rb_rotate_right(other, root);
					other = parent->rb_right;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				if (other->rb_right)
					rb_set_black(other->rb_right);
				__rb_rotate_left(parent, root);
				node = root->node;
				break;
			}
		} else {
			other = parent->rb_left;

			if (rb_is_red(other)) {
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_right(parent, root);
				other = parent->rb_left;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
				(!other->rb_right || rb_is_black(other->rb_right))) {
				rb_set_red(other);
				node = parent;
				parent = rb_parent(parent);
				
			} else {
				if (!other->rb_left || rb_is_black(other->rb_left)) {
					rb_set_black(other);
					if (other->rb_right)
						rb_set_black(other->rb_right);
					__rb_rotate_left(other, root);
					other = other->rb_right;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				if (other->rb_left)
					rb_set_black(other->rb_left);
				__rb_rotate_right(parent, root);
				node = root->node;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node);
}

void rb_erase(rb_node_t *node, rb_root_t *root)
{
	rb_node_t *child, *parent;
	int color;

	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else {
		rb_node_t *next = NULL, *old = node;
		int tmp;

		next = node->rb_right;
		while (next->rb_left)
			next = next->rb_left;
		tmp = old->data;
		old->data = next->data;
		next->data = tmp;

		node = next;
	}

	parent = rb_parent(node);
	if(child)
		rb_set_parent(child, parent);
	if (parent) {
		if (node == parent->rb_left)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	} else 
		root->node = child;

	color = rb_color(node);
	if (RB_BLACK == color)
		__rb_erase_color(child, parent, root);
}

